# To change this template, choose Tools | Templates
# and open the template in the editor.
#
# todo
#   +function to create sudokus

__author__="martin"
__date__ ="$04.04.2010 12:38:24"

import numpy
import sys


size=9
ok=1
nok=0
pop_size=50
mutation_rate=9
injection_rate=5

def create_sudoku(parent, num_fields):
    mat=numpy.zeros([size, size])
    n=0
    x=numpy.random.randint(size)
    y=numpy.random.randint(size)
    mat[y, x]=numpy.random.randint(size)
    mat=solve_sudoku(parent,mat)
    while n < (size**2-num_fields):
        x=numpy.random.randint(size)
        y=numpy.random.randint(size)
        if mat[y, x]!=0:
            mat[y, x]=0
            n+=1
    return mat

def control_row(mat, y, x):
    res=1
    for yi in xrange(0, size):
        if yi!=y:
            if mat[yi, x]==mat[y, x]:
                res=0
    return res

def control_column(mat, y, x):
    res=1
    for xi in xrange(0, size):
        if xi!=x:
            if mat[y, xi]==mat[y, x]:
                res=0
    return res

def control_quadrat(mat, y, x):
    res=1
    xbegin=int(x/3)*3
    xend=xbegin+3
    ybegin=int(y/3)*3
    yend=ybegin+3
    for xi in xrange(xbegin, xend):
        for yi in xrange(ybegin, yend):
            if xi!=x or yi!=y:
                if mat[yi, xi]==mat[y, x]:
                    res=0
    return res

def control_mat(mat):
    res=ok
    x=0
    y=0
    while res and x < size and y < size:
        loesungen=range(1, size+1)
        if mat[y, x]== 0.0:
            loesungen=check_row(mat, y, x, loesungen)
            loesungen=check_column(mat, y, x, loesungen)
            #print loesungen
            loesungen=check_quadrat(mat, y, x, loesungen)
            #print loesungen
            if len(loesungen) < 1:
                #print x,y,mat[y, x],loesungen
                res=nok
        else:
            if res:
                res=control_row(mat, y,x)
                if res:
                    res=control_column(mat, y, x)
                    if res:
                        res=control_quadrat(mat, y, x)
        x+=1
        if x>=size:
            y+=1
            x=0
    return res

def error_msg(text):
    print text

def save_sudoku(filename, mat):
    try:

        file=open(filename, "w")
    except:
        error_msg("could not open file!")
        return nok
    for y in xrange(0, size):
        h=str(int(mat[y, 0]))
        for x in xrange(1, size):
            h+=","+str(int(mat[y, x]))
        h+="\n"
        file.write(h)
    file.close()
    return ok

def load_sudoku(filename):
    mat=numpy.zeros([size, size])
    try:

        file=open(filename)
    except:
        error_msg("file not found!")
        return mat
    i=0
    for line in file:
        numbers=line.strip().split(",")
        j=0
        for e in numbers:
            mat[i, j]=int(e)
            j+=1
        i+=1
    return mat

def check_row(mat, i, j, loesungen):
    n=0
    for n in range(0, size):
        e=mat[n, j]
        if e in loesungen:
            loesungen.remove(e)
    return loesungen

def check_column(mat, i, j, loesungen):
    for n in range(0, size):
        e=mat[i, n]
        if e in loesungen:
            loesungen.remove(e)
    return loesungen

def check_quadrat(mat, i, j, loesungen):
    if 0 <= i <= 2:
        irange=[0, 1, 2]
    elif 3<= i <=5:
        irange=[3, 4, 5]
    else:
        irange=[6, 7, 8]
    if 0 <= j <= 2:
        jrange=[0, 1, 2]
    elif 3<= j <=5:
        jrange=[3, 4, 5]
    else:
        jrange=[6, 7, 8]
    for n in irange:
        for m in jrange:
            e=mat[n, m]
            if e in loesungen:
                loesungen.remove(e)
    return loesungen


def solve_sudoku(parent=None, omat=numpy.zeros([size, size])):
    #mat=load_sudoku(fname)
    #print mat
    mat=omat.copy()
    loesungen=range(1, size+1)
    solved=0
    index_l=0
    index_s=0
    min_i=0
    min_j=0
    mat_saved=list([])
    if parent!=None:
        parent.generate_progress_dialog(100)
    pc=0
    while not solved:
        solved=1
        simple=0
        min_l=9
        delete_branch=0
        #print mat
        if parent!=None:
            parent.show_progress(pc)
            if pc < 100:
                pc+=1
            else:
                pc=0
        for i in range(0, size):
            for j in range(0, size):
                loesungen=range(1, size+1)
                if mat[i, j]== 0:
                    solved=0
                    loesungen=check_row(mat, i, j, loesungen)
                    loesungen=check_column(mat, i, j, loesungen)
                    loesungen=check_quadrat(mat, i, j, loesungen)

                    if len(loesungen)==1:
                        #print loesungen,
                        simple=1
                        mat[i, j]=loesungen[0]
                    if len(loesungen)==0:
                        delete_branch=1
                        #print i, j, mat[i, j], mat


                            
                            
                    if 1< len(loesungen) < min_l:
                        min_i=i
                        min_j=j
                        min_l=len(loesungen)
                        index_l=0
        if delete_branch:
            index_s=len(mat_saved)-1
            #print mat_saved
            ok=1
            if (len(mat_saved[index_s]["loesungen"]) <= 1):
                mat_saved.pop()
                index_s=len(mat_saved)-1

            if index_s >= 0:
                #print index_s, mat_saved[index_s]

                if len(mat_saved[index_s]["loesungen"]) > 1:
                    l=mat_saved[index_s]["loesungen"][0]
                    mat_saved[index_s]["loesungen"].remove(l)
                    mat=mat_saved[index_s]["mat"]
                    min_i=mat_saved[index_s]["min_i"]
                    min_j=mat_saved[index_s]["min_j"]
                    mat[min_i, min_j]=mat_saved[index_s]["loesungen"][0]
                #print index_s,mat_saved[index_s]
                simple=0
                index_l+=1
        elif not simple and not delete_branch and not solved:
            #solved=0
            loesungen=range(1,10)
            loesungen=check_row(mat, min_i, min_j, loesungen)
            loesungen=check_column(mat, min_i, min_j, loesungen)
            loesungen=check_quadrat(mat, min_i, min_j, loesungen)
            if len(loesungen) > 0:
                #index_s+=1
                d=dict([])
                d["mat"]=mat.copy()
                d["min_i"]=min_i
                d["min_j"]=min_j
                d["loesungen"]=loesungen

                mat_saved.append(d)
                
                mat[min_i, min_j]=loesungen[0]
    if parent!=None:
        parent.close_progress_dialog()
    return mat

def solve_sudoku_ga(parent=None, omat=numpy.zeros([size, size]), nrounds=100, recombination_method=0, mutation_method=0, select_method=0):
    
    def calc_pop_varianz(pop):
        i =0
        d=0
        for n in xrange(0, len(pop)-1):
            for m in xrange(n+1, len(pop)-1):
                i+=1
                d+=sum(sum((pop[n]-pop[m])**2))
        return d/float(i)
        
    def init_pop(omat):
        pop=list()
        for n in xrange(0, pop_size):
            pop.append(omat.copy())
            for x in xrange(0, size):
                for y in xrange(0, size):
                    if pop[n][x, y]==0:
                        temp=get_random_solution(pop[n], x, y)
                        pop[n][x, y]=temp
        return pop
    
    def get_xy():
        x=numpy.random.randint(0, size)
        y=numpy.random.randint(0, size)
        return x, y

    def get_random_solution(mat, x, y):
        l=range(1, size+1)
        l=check_row(mat, x, y, l)

        if l!=[]:
            if len(l) > 1:
                n=numpy.random.randint(0, len(l)-1)
            else:
                n=0
            temp=l[n]
        else:
            temp=numpy.random.randint(1,size)
        return temp
    
    def mutate_mat(omat, mat):
        x, y=get_xy()
        if 0<mat[x,y]<9:
            mat[x,y]+=1
        return mat
                 
    def mutate_mat1(omat, mat):
        x, y=get_xy()
        while omat[x,y]!=0:
            x, y=get_xy()
        temp=get_random_solution(mat, x, y)

       
        mat[x, y]=temp
        return mat
    
    def swap_mat(mat, x, y, xn, yn):
        t=mat[x,y]
        mat[x,y]=mat[xn,yn]
        mat[xn,yn]=t
        return mat
        
    def mutate_mat2(omat, mat):
        x, y=get_xy()
        while omat[x,y]!=0:
            x, y=get_xy()
        xn, yn=get_xy()
        n=0
        while (((omat[xn,y]!=0)) or (mat[xn, y]==mat[x,y])) and (n < 10):            
            xn, yn=get_xy()
            n+=1
        #print omat[xn, y],mat[x,y], mat[xn,y],(omat[xn,y]!=0) , (mat[x,y]== mat[xn,y])
        if (omat[xn,y]==0):
            mat=swap_mat(mat, x, y, xn, y)
            
        return mat
       
    def mutate_mat3(omat, mat):
        x, y=get_xy()
        while (omat[x,y]!=0):
            #print unique_list(mat[x,:])
            x, y=get_xy()
        xn, yn=get_xy()
        while (omat[xn,y]!=0):
            xn, yn=get_xy()
        mat=swap_mat(mat, x, y, xn, y)        
        return mat

    def mutate_mat4(omat, mat):
        x, y=get_xy()
        while omat[x,y]==0:
            x, y=get_xy()
        temp=numpy.random.randint(1,size)

       
        mat[x, y]=temp
        return mat
    
    def mutate_mat5(omat, mat):
        x, y=get_xy()
        while omat[x,y]==0:
            x, y=get_xy()
        temp=mat[x,y]
        if temp < 9:
            temp+=1
        else:
            temp=1

       
        mat[x, y]=temp
        return mat    
    
    def mutate_mat6(omat, mat):
        x, y=get_xy()
        while omat[x,y]==0:
            x, y=get_xy()
        temp=numpy.random.randint(1, size)

       
        mat[x, y]=temp
        return mat    

    def mutate_mat7(omat, mat):
        x, y=get_xy()
        while (omat[x,y]!=0):
            #print len(unique_list(mat[:,y]))
            #print unique_list(mat[x,:])
            x, y=get_xy()
        xn, yn=get_xy()
        n=0
        while ((omat[x,yn]!=0)  or (mat[x,y]==mat[x,yn])) and (n < 10):
            n+=1
            xn, yn=get_xy()
        if omat[x, yn]==0:
            mat=swap_mat(mat, x, y, x, yn)        
        return mat

    def mutate_mat8(omat, mat):   
        if numpy.random.randint(1,2)==1:
            m=mutate_mat2(omat, mat)
        else:
            m=mutate_mat7(omat, mat)
        return m   
    
    def select_mutation(nr, omat, mat):
        if (nr==0):
            mat=mutate_mat(omat, mat) 
        elif (nr==1):
            mat=mutate_mat1(omat, mat)
        elif (nr==2):
            mat=mutate_mat2(omat, mat)
        elif (nr==3):
            mat=mutate_mat3(omat, mat)
        elif (nr==4):
            mat=mutate_mat4(omat, mat)    
        elif (nr==5):
            mat=mutate_mat5(omat, mat)
        elif (nr==6):
            mat=mutate_mat6(omat, mat)
        elif (nr==7):
            mat=mutate_mat7(omat, mat)
        elif (nr==8):
            mat=mutate_mat8(omat, mat)
        return mat
                                                                                                
     
    def score_mat(omat, mat):
        score=0
        for x in xrange(0, size):
            for y in xrange(0, size):
                if omat[x, y]!=0:
                    if mat[x,y]!=omat[x,y]:
                        score+=1
                #check rows
                a=mat[x,:]
                for n in a:
                    if n==mat[x,y]:
                        score+=1
                #check columns
                a=mat[:,y]
                for n in a:
                    if n==mat[x,y]:
                        score+=1
                #check quadrats
                xb=x/3
                yb=y/3
                for xn in xrange(xb, xb+3):
                    for yn in xrange(yb, yb+3):
                        if mat[xn, yn]==mat[x,y]:
                            score+=1
                score-=3

        return score
    
    def fac(l):
        e=1
        #print l
        for n in xrange(0, len(l)):
            e*=l[n]
        return e
    
    def score_mat2(mat):
        score=0
        l=numpy.arange(1,size+1)
        l=l.astype(float)
        lf=fac(l)
        for x in xrange(0, size):
            score+=abs(lf-fac(mat[x,:].flatten()))
        for y in xrange(0, size):
           score+=abs(lf-fac(mat[:,y].flatten()))
        for i in xrange(0,3):
           for j in xrange(0,3):
               score+=abs(lf-fac(mat[i*3:(i+1)*3, j*3:(j+1)*3].flatten()))
        #print score
        return score
    
    def unique_list(l):
        l2=list()
        for e in l:
            if not(e in  l2):
                l2.append(e)
        return l2
    
    def score_mat3(mat):
        #print mat
        score=0
        l=numpy.arange(1,size+1)
        l=l.astype(float)
        lf=sum(l)
        for x in xrange(0, size):
            score+=abs(lf-sum(mat[x,:].flatten()))
            ms=unique_list(mat[x,:].flatten())
            score+=10*abs(9- len(ms))
        for y in xrange(0, size):
            score+=abs(lf-sum(mat[:,y].flatten()))
            ms=unique_list(mat[:,y].flatten())
            score+=10*abs(9- len(ms))
        for i in xrange(0,3):
           for j in xrange(0,3):
               score+=abs(lf-sum(mat[i*3:(i+1)*3, j*3:(j+1)*3].flatten()))
               ms=unique_list(mat[i*3:(i+1)*3, j*3:(j+1)*3].flatten())
               score+=10*abs(9-len(ms))
        #print score
        return score 
    
    def score_mat5(mat):
        #print mat
        score=0
        for x in xrange(0, size):
            #score+=abs(lf-sum(mat[x,:].flatten()))
            ms=unique_list(mat[x,:].flatten())
            score+=10*abs(9- len(ms))
        for y in xrange(0, size):
            #score+=abs(lf-sum(mat[:,y].flatten()))
            ms=unique_list(mat[:,y].flatten())
            score+=10*abs(9- len(ms))
        for i in xrange(0,3):
           for j in xrange(0,3):
               #score+=abs(lf-sum(mat[i*3:(i+1)*3, j*3:(j+1)*3].flatten()))
               ms=unique_list(mat[i*3:(i+1)*3, j*3:(j+1)*3].flatten())
               score+=10*abs(9-len(ms))
        #print score
        return score 
    
    def score_mat4(mat):
        #print mat
        score=0
        l=numpy.arange(1,size+1)
        l=l.astype(float)
        lf=sum(l)
        for x in xrange(0, size):
            score+=abs(lf-sum(mat[x,:].flatten()))
            ms=unique_list(mat[x,:].flatten())
            score+=10*abs(9- len(ms))
        for y in xrange(0, size):
            score+=abs(lf-sum(mat[:,y].flatten()))
            ms=unique_list(mat[:,y].flatten())
            score+=10*abs(9- len(ms))
            
        return score
    
    def recombination_mat(mat1, mat2):
        a=mat1.copy()
        b=mat2.copy()

        x, y=get_xy()
        for i in xrange(0, size):
            for j in xrange(0, size):
                if i > x:
                    if j > y:
                        a[x, y]=mat2[x,y]
                        b[x, y]=mat1[x,y]
        return a, b
    
    def recombination_mat2(mat1, mat2):
        a=mat1.copy()
        b=mat2.copy()

        x, y=get_xy()
        for i in xrange(0, x):
            a[i]=mat2[i]
            b[i]=mat1[i]
        return a, b
    
    def recombination_mat3(mat1, mat2):
        a=mat1.copy()
        b=mat2.copy()
        for x in xrange(0, size):
            for y in xrange(0, size):
                if numpy.random.uniform() < 0.5:
                    a[x,y]=mat2[x,y]
                    b[x,y]=mat1[x,y]
        return a, b

    def recombination_mat4(mat1, mat2):
        #3 point crossover
        a=mat1.copy()
        b=mat2.copy()
        x2=0
        y2=0
        x, y=get_xy()
        while (x2 <= x) and (y2 < y):
            #print x2, y2, x, y
            x2, y2=get_xy()
        for i in xrange(0, size):
            for j in xrange(0, size):
                if (i > x) and (i < x2):
                    if (j > y) and (j < y2):
                        a[x, y]=mat2[x,y]
                        b[x, y]=mat1[x,y]
        return a, b
    
    
    def select_recombination(nr, mat1, mat2):
        a=mat1
        b=mat2
        if (nr==1):
            a, b=recombination_mat(mat1, mat2)
        elif (nr==2):
            a, b=recombination_mat2(mat1, mat2)
        elif (nr==3):
            a, b=recombination_mat3(mat1, mat2)
        elif (nr==4):
            a, b=recombination_mat4(mat1, mat2)
        return a, b            
    def get_best_score(score):
        b=81*9*8*7*6*5*4*3*2
        bn=0
        for n in xrange(0, len(score)):
            if score[n] < b:
                b=score[n]
                bn=n
        return b, bn
    
    def get_worst_score(score):
        b=0
        bn=0
        for n in xrange(0, len(score)):
            if score[n] > b:
                b=score[n]
                bn=n
        return b, bn
    
    def calc_fitness(pop, omat):
        s=list()
        for n in xrange(0, len(pop)):
            s.append(score_mat5(pop[n]))
        #print s
        return s

    def calc_fitness2(pop, omat,n):
        s=list()
        T=1/float(n)
        k=10**6
        for n in xrange(0, len(pop)):
            s.append(numpy.exp(1*(score_mat5(pop[n]))/(T*k)))
        #print s
        return s
    
    def selection(pop, c_pop, score, c_score, omat):
        #idea only keep parent if his fitness is better than all the childs    
        #print c_pop
        #score=calc_fitness(pop, omat)
        #c_score=calc_fitness(c_pop, omat)
        #print score
        for n in xrange(0, pop_size):
            m=0
            #print score
            cs, ci=get_best_score(c_score)
            if (score[n] > cs):
                pop[n]=c_pop[m]
                c_pop.pop(m)
                score[n]=c_score[m]
                c_score.pop(m)
          
        best_score, best_ind=get_best_score(score)
        #print best_score
        return pop, score
    
    def selection2(pop, c_pop, score, c_score, omat):
        #idea only keep best parent throw away worst child    
        #score=calc_fitness(pop, omat)
        #c_score=calc_fitness(c_pop, omat)
        bs, bi=get_best_score(score)
        pop[0]=pop[bi]
        score[0]=score[bi]
        ws, wi=get_worst_score(c_score)
        m=0
        for n in xrange(1, pop_size):
            if m!=wi:
                pop[n]=c_pop[m]
                score[n]=c_score[m]
                
            m+=1
            
        #best_score, best_ind=get_best_score(score)
        #print best_score
        return pop, score
    
    def selection3(pop, c_pop, score, c_score, omat):
        #idea only keep best parent throw away worst child    
        #score=calc_fitness(pop, omat)
        #c_score=calc_fitness(c_pop, omat)
        npop=list()
        n_score=list()
        for n in xrange(0, injection_rate):
            bs, bi=get_best_score(score)
            npop.append(pop.pop(bi).copy())
            n_score.append(score.pop(bi))
            
        for n in xrange(injection_rate, pop_size):
            bs, bi=get_best_score(c_score)
            npop.append(c_pop.pop(bi).copy())
            n_score.append(c_score.pop(bi))
        #print len(npop)    
        #best_score, best_ind=get_best_score(score)
        #print best_score
        return npop, n_score
    
    def selection4(pop, c_pop, score, c_score, omat):
        #idea use best children for next generation 
        #score=calc_fitness(pop, omat)
        #c_score=calc_fitness(c_pop, omat)
        npop=list()
        n_score=list()

            
        for n in xrange(0, pop_size):
            bs, bi=get_best_score(c_score)
            npop.append(c_pop.pop(bi).copy())
            n_score.append(c_score.pop(bi))
        #print len(npop)    
        #best_score, best_ind=get_best_score(score)
        #print best_score
        return npop, n_score

    def selection5(pop, c_pop, score, c_score, omat):
        #idea tournament between children and parent pop
        #score=calc_fitness(pop, omat)
        #c_score=calc_fitness(c_pop, omat)
        npop=list()
        n_score=list()

            
        for n in xrange(0, pop_size):
            i=numpy.random.randint(0, len(c_pop)-1)
            #print i, len(c_score)
            if score[n] < c_score[i]:
                n_ind=pop[n].copy()
                n_s=score[n]
            else:
                n_ind=c_pop[i].copy()
                n_s=c_score[i]
            npop.append(n_ind)
            n_score.append(n_s)
        #print len(npop)    
        #best_score, best_ind=get_best_score(score)
        #print best_score
        return npop, n_score
    
    def choose_select_method(nr, pop, c_pop, score, c_score, omat):
        if (nr==0):
            npop, nscore=selection(pop, c_pop, score, c_score, omat)
        elif (nr==2):
            npop, nscore=selection2(pop, c_pop, score, c_score, omat)
        elif (nr==3):
            npop, nscore=selection3(pop, c_pop, score, c_score, omat)     
        elif (nr==4):
            npop, nscore=selection4(pop, c_pop, score, c_score, omat)
        elif (nr==5):
            npop, nscore=selection5(pop, c_pop, score, c_score, omat)
        return npop, nscore                              
        
    def distance_ind(i, j):
        d=sum(sum((i-j)**2))
    
    numpy.random.seed(0)                        
    pop=init_pop(omat)
    #print pop
    #cpop=init_pop(omat)
    score=calc_fitness(pop, omat)

    best_score=size**4
    rounds=0
    if parent!=None:
        parent.generate_progress_dialog(nrounds)
    pc=0
    while best_score > 0 and rounds < nrounds:
        cpop=list()
        if parent!=None:
            parent.show_progress(rounds)

        for n in xrange(0, pop_size):
           if rounds%2==0:
               #print "crossover"
               #print len(cpop), len(pop)
               d=0
               while d== 0:
                   m=numpy.random.randint(0, pop_size-1)
                   d=distance_ind(pop[m], pop[n])
                   #print d
               a, b=select_recombination(recombination_method, pop[n].copy(), pop[m].copy())
               cpop.append(a)
               cpop.append(b)
               #cpop.append(pop[n].copy())
           else:
               #print "mutation"
               mn=numpy.random.randint(1,mutation_rate)
               #print mn
               c=pop[n].copy()
               for i in xrange(0, mn):
                   #print cpop[n]
                   c=select_mutation(mutation_method, omat, c)
               cpop.append(c)
        
        score=calc_fitness(pop, omat)#
        #score=calc_fitness2(pop, omat, rounds+1)
        c_score=calc_fitness(cpop, omat)#
        #c_score=calc_fitness2(cpop, omat, rounds+1)
        #print len(cpop)
        pop, score=choose_select_method(select_method,pop, cpop, score, c_score, omat)
        #print len(pop)
        #print pop[0]
        #score=calc_fitness(pop, omat)
        #print score
        #pop, score=evolve_pop(pop, score)
        
        best_score, best_ind=get_best_score(score)
        best_score=score_mat5(pop[best_ind])
        #pop[0]=pop[best_ind]
        #score[0]=best_score
        if output and rounds%10==0:
            v=calc_pop_varianz(pop)
            print "generation ", rounds, " fitness ", best_score, " varianz ", v
            #print pop[best_ind]
        rounds+=1
        #print rounds
    if output:
        print "generation ", rounds, " fitness ", best_score
    if parent!=None:
        parent.close_progress_dialog()
    return pop[best_ind]
            
        

                        

def test(r):

    mat=load_sudoku("sudoku_easy.txt")
    print mat

    mat=solve_sudoku_ga(None, mat, int(r), 5, 2, 3)
    print mat
    mat=load_sudoku("sudoku_106.txt")
    print mat
    mat=solve_sudoku_ga(None, mat, int(r), 5, 2, 3)
    print mat
    mat=load_sudoku("sudoku2.txt")
    print mat
    mat=solve_sudoku(None, mat)
    print mat
    mat=load_sudoku("sudoku_106.txt")
    mat=solve_sudoku(None, mat)
    print mat

def main(fname):
    mat=solve_sudoku(None, fname)
    print mat

if __name__ == "__main__":
    output=1
    test(500)
else:
    output=0

